package demo;

import java.util.LinkedList;
import java.util.Queue;

public class Test {
    class ListNode{
        public int val;
        public ListNode next;
        public ListNode(int val) {
            this.val = val;
        }

        @Override
        public String toString() {
            return "ListNode{" +
                    "val=" + val +
                    '}';
        }
    }
    public ListNode head;
    public void createList() {
        ListNode node1 = new ListNode(11);
        ListNode node2 = new ListNode(54);
        ListNode node3 = new ListNode(23);
        ListNode node4 = new ListNode(45);
        head = node1;
        node1.next = node2;
        node2.next = node3;
        node3.next = node4;
    }
    public static ListNode partition(ListNode pHead, int x) {
        // write code here
        Queue<ListNode> queue1 = new LinkedList<>();
        Queue<ListNode> queue2 = new LinkedList<>();
        ListNode cur = pHead;
        while(cur != null) {
            if(cur.val < x) {
                queue1.offer(cur);
            }else{
                queue2.offer(cur);
            }
            cur = cur.next;
        }
        cur = pHead;
        while(!queue1.isEmpty()) {
            cur.next = queue1.poll();
            cur = cur.next;
        }
        while(!queue2.isEmpty()) {
            cur.next = queue2.poll();
            cur = cur.next;
        }
        return pHead;
    }

    public static void main(String[] args) {
        Test test = new Test();
        test.createList();
        System.out.println(partition(test.head, 23));
    }
}
